#ifndef QUICKSORT_H
#define QUICKSORT_H

#include "sortalgorithm.h"
#include <stack>

// 快速排序类，继承自抽象基类 SortAlgorithm
class QuickSort : public SortAlgorithm {
public:
    // 构造函数，接受初始数据并初始化栈结构
    QuickSort(const QVector<int> &values);

    // 每次排序执行一步
    void step() override;

    // 判断排序是否完成
    bool isFinished() const override;

    // 获取当前排序数据（带颜色）
    const QVector<SortBar>& getData() const override;

    // 获取并重置比较次数
    int getAndResetCompareCount() override;

    // 获取并重置交换次数
    int getAndResetSwapCount() override;

    // 返回复杂度信息
    QString getComplexityInfo() const override;

    // 设置排序顺序（升序或降序）
    void setOrder(SortOrder order) override;

private:
    // 当前排序数据，每个元素带颜色信息
    QVector<SortBar> bars;

    // 表示当前正在处理的快排区间状态帧
    struct Frame {
        int low;        // 区间起始索引
        int high;       // 区间结束索引
        int state;      // 当前处理状态（0=初始化，1=分区进行中，2=交换pivot）
        int i;          // 用于分区时指向较小元素位置
        int j;          // 分区过程中向右扫描的指针
        int pivotIndex; // 当前 pivot 元素的索引
    };

    // 使用栈管理多个递归帧，实现非递归的快速排序
    std::stack<Frame> stack;

    // 比较次数
    int compareCount = 0;

    // 交换次数
    int swapCount = 0;

    // 当前排序方向
    SortOrder sortOrder = SortOrder::Ascending;

    // 工具函数：交换两个元素并记录交换次数
    void swapBars(int i, int j);

    // 将所有元素颜色重置为默认灰色
    void resetColors();
};

#endif // QUICKSORT_H
